1. Field of the Invention
The resent invention generally relates to the art of microelectronic integrated circuits, and more specifically to a physical design automation system and process for designing integrated circuit chips using multiway partitioning with constraints.
2. Description of the Related Art
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. However, it is expected that the feature size can be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space of a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield. The arrangement of individual cells in an integrated circuit chip is known as a cell placement.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnect wire network or net. A goal of the optimization process is to determine a cell placement such that all of the required interconnects can be made, and the total wirelength and interconnect congestion are minimized.
Prior art methods for achieving this goal comprise generating one or more initial placements, modifying the placements using optimization methodologies including Genetic Algorithms such as simulated evolution, force directed placement or simulated annealing, and comparing the resulting placements using a cost criteria.
In conventional chip design, the positions of certain "unmovable" cells (external interconnect terminals or pads, large "megacells" etc.) will be fixed a priori by the designer. Given those fixed positions, the rest of the cells are then placed on the chip. Since the unmovable cells and pads are located or placed before the placement for the rest of the cells of chip has been decided on, it is unlikely that the chosen positions will be optimal.
In this manner, a number of regions, which may have different sizes and shapes, are defined on the chip for placement of the rest of the cells.
It is desirable to assign individual microelectronic devices or cells to the regions, or "partition" the placement such that the total interconnect wirelength is minimized. However, methodologies for accomplishing this goal efficiently have not been proposed heretofore.
The general partitioning methodology is to hierarchically partition a large circuit into a group of smaller subcircuits until each subcircuit is small enough to be designed efficiently. Because the quality of the design may suffer due to the partitioning, the partitioning of a circuit has to be done carefully.
One of the most common objectives of partitioning is to minimize the cutsize which is defined as a number of nets crossing a cut. Also the number of partitions often appears as a constraint with upper and lower bounds. At chip level, the number of partitions is determined, in part, by the capability of the placement algorithm.
The prior art accomplishes partitioning by means of a series of "bipartitioning" problems, in which a decision is made to assign a component to one of two regions. Each component is hierarchically bipartitioned until the desired number of components is achieved. Group migration algorithms such as Kernighan-Lin "min-cut" algorithm and its extensions and the applications of the simulated annealing and simulated evolution to the partitioning problem do not take into account the relative positions of future partitions on the plane.
The Kernighan-Lin algorithm is described in "An Efficient Heuristic Procedure for Partitioning Graphs", W. Kernighan and S. Lin, Bell System Technical Journal, 49, pp. 291-307, 1970. Its extensions are described in "A Linear Time Heuristics for Improving Network Partitions", C. M. Fiduccia and R. M. Mattheyses, Proc. of the 19th Design Automation Conference, pp. 175-181, 1982; "A Cell Replicating Approach to Mincut Based Circuit Partitioning", C. Kring and A. R. Newton, Proc. of IEEE International Conf. on CAD, pp. 2-5 1991; and "Towards Efficient Hierarchical Designs by Ratio Cut Partitioning", Y. Wei and C. Cheng, International Conf. on CAD, pp. 298-301, 1989.
Simulated annealing is described in "Equation of State Calculations by Fast Computing Machines", N. Metropolis, A. Rosenbluth and M. Rosenbluth, Journal of Chemistry and Physics, pp. 1087-1092, 1993. Simulated evolution is described in "Stochastic Evolution: A Fast Effective Heuristic for Some Generic Layout Problems", Y. Saab and V. Rao, Proc. of Design Automation Conference, pp. 26-31, 1990.
These algorithms can not simultaneously solve the partitioning problem and the problem of placing partitions on the chip, and thereby their applicability to physical design automation systems for integrated circuit chip design is limited.